//https://leetcode.cn/problems/binary-tree-inorder-traversal/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        stack<TreeNode*> st;
        vector<int> ret;

        while (cur || !st.empty())
        {
            //左路节点入栈
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            //带右子树入栈并访问左节点
            TreeNode* top = st.top();
            st.pop();

            ret.push_back(top->val);

            //转化为右子树的子问题
            cur = top->right;
        }

        return ret;

    }
};